#include <iostream>
#include <stdio.h>

#include <iostream>
#include <vector>

class Solution {
private:
    std::vector<std::string> result;

    void backtracking (std::string& s, int start, int pointNum) {
        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
        if (pointNum == 3) {
            if(isVauld(s, start, s.size() - 1))  //第四个是否合法
                result.push_back(s);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isVauld(s, start, i)) {   // 是否合格
                // 获取[start,i]在s中的子串
                s.insert(s.begin() + i + 1, '.');//在点i后面插入一个.
                pointNum++;
                backtracking(s, i + 2, pointNum); // 寻找i+1为起始位置的子串
                pointNum--;
                s.erase(s.begin() + i + 1);
            } else {                                // 不是合法，结束本次循环
                break;
            }
            
        }
    }
    bool isVauld(const std::string& s, int start, int end) {
        if(start > end){
            return false;
        }

        if(s[start] == '0' && start != end){
            return false;
        }
        int num = 0;
        for(int i = start; i <= end; i++){
            if(s[i] > '9' || s[i] < '0'){
                return false;
            }
            num = num*10 + (s[i] - '0');
            if(num > 255){
                return false;
            }
        }
        return true;
    }
public:
    std::vector<std::string> restoreIpAddresses(std::string s) {
        result.clear();
        if(s.size() > 12) return result;
        backtracking(s, 0,0);
        return result;
    }
};

int main(int argv, char**argc)
{

    printf("************  test hello zc!!!   **************\n");
    /* add test code! */
    Solution solve;
    std::vector<std::string> ret;
    ret = solve.restoreIpAddresses("25525511135");
    printf("[ \n");
    for(auto p:ret){
        printf("[");
        printf("%s", p.data());
        printf("] ");    
    }
    printf("]\n");
    return 0;
}
